
package org.sevenblindmice.make24;

import java.util.Arrays;

public class Validator {

    @SuppressWarnings("serial")
    private static class ParsingException extends Exception {
        public ParsingException(String detailMessage) {
            super(detailMessage);
        }
    }

    enum Token {
        NUMBER, OP, PAREN, END,
    }

    // Precedence
    private final int ADDITIVE = 1;
    private final int MULTIPLICATIVE = 2;

    private final int[] numbers;
    private final String input;
    private String error;
    private int index = 0;
    private int lastIndex = 0;
    private int value;

    public Validator(int[] numbers, String input) {
        this.numbers = numbers;
        this.input = input == null ? "" : input;
    }

    public boolean validate() {
        try {
            int exp = expression();
            if (nextToken() != Token.END) {
                throw new ParsingException("unexpected input");
            }
            if (24 != exp) {
                error = "the value is " + exp;
                return false;
            }
        } catch (ParsingException e) {
            error = e.getMessage() + " at index " + lastIndex;
            if (lastIndex < input.length()) {
                error += ": " + input.charAt(lastIndex);
            }
            return false;
        }
        error = "";
        return true;
    }

    private int expression() throws ParsingException {
        return expression(primary(), 0);
    }

    private int expression(int lhs, int minPrecedence) throws ParsingException {
        while (true) {
            Token token = peekToken();
            if (token != Token.OP) {
                break;
            }
            char op = input.charAt(lastIndex);
            int precedence = getPrecedence(op);
            if (precedence < minPrecedence) {
                break;
            }

            nextToken(); // Consume the op token
            int rhs = primary();
            while (true) {
                Token newToken = peekToken();
                if (newToken != Token.OP) {
                    break;
                }
                char newOp = input.charAt(lastIndex);
                int newPrecedence = getPrecedence(newOp);
                if (precedence < newPrecedence) {
                    rhs = expression(rhs, newPrecedence);
                } else {
                    break;
                }
            }

            lhs = doOp(op, lhs, rhs);
        }
        return lhs;
    }

    private Token peekToken() throws ParsingException {
        Token token = nextToken(); // look-ahead!
        index = lastIndex; // rewind look-ahead
        return token;
    }

    private int doOp(char op, int lhs, int rhs) throws ParsingException {
        switch (op) {
            case '+':
                return lhs + rhs;
            case '-':
                return lhs - rhs;
            case '*':
                return lhs * rhs;
            case '/':
                if (lhs % rhs != 0) {
                    throw new ParsingException(lhs + " is not divisible by " + rhs);
                }
                return lhs / rhs;
        }
        throw new ParsingException(op + " is an invalid operator");
    }

    private int getPrecedence(char op) {
        if (op == '*' || op == '/') {
            return MULTIPLICATIVE;
        }
        if (op == '+' || op == '-') {
            return ADDITIVE;
        }
        return -1;
    }

    private int primary() throws ParsingException {
        Token token = nextToken();
        switch (token) {
            case NUMBER:
                if (Arrays.binarySearch(numbers, value) < 0) {
                    throw new ParsingException(value + " is not a given number");
                }
                // TODO: Check each number used once and only once
                return value;
            case PAREN:
                if (input.charAt(lastIndex) == '(') {
                    int exp = expression();
                    if (nextToken() != Token.PAREN || input.charAt(lastIndex) != ')') {
                        throw new ParsingException("unmatched '('");
                    }
                    return exp;
                }
                throw new ParsingException("unexpected symbol");
            default:
                throw new ParsingException("incomplete expression");

        }
    }

    private Token nextToken() throws ParsingException {
        value = 0;
        lastIndex = index;
        boolean isNumber = false;
        while (index < input.length()) {
            char c = input.charAt(index++);
            if (c >= '0' && c <= '9') {
                isNumber = true;
                value = c - '0' + 10 * value;
            } else {
                if (isNumber) {
                    index--;
                    break;
                }

                switch (c) {
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                        return Token.OP;
                    case '(':
                    case ')':
                        return Token.PAREN;
                    default:
                        throw new ParsingException("invalid input");
                }
            }
        }

        if (isNumber) {
            return Token.NUMBER;
        }
        return Token.END;
    }

    public String getError() {
        return error;
    }
}
